package leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * You may assume that each input would have exactly one solution, and you may not use the same element twice.
 * Given nums = [2, 7, 11, 15], target = 9,
 * Because nums[0] + nums[1] = 2 + 7 = 9,
 * return [0, 1].
 * Created by hao on 17-3-21.
 */
public class TwoSum {
    /**
     * 遍历法
     * 所有元素两两相加，判断是否等于目标值
     * 优化方向主要在减少遍历次数
     * 首当其冲的是实现每两个元素忽略顺序的情况下最多只相加一次
     * <p>
     * 时间复杂度 O(N^2)
     *
     * @param numbers
     * @param target
     * @return
     */
    public static int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[2];
    }

    /**
     * 效率更高
     * 思路：
     * 1. 遍历到第一个元素时，计算它和哪个数值相加等于目标值，把这个数值作为key，当前元素索引作为value放入map中
     * 2. 从第二个元素开始遍历时，先去查找map中有没有一个key等于当前遍历到的元素，
     * a). 如果有，则说明之前遍历过的某个元素(值表现为map的key，索引表现为map的value)和当前遍历到的元素相加等于目标值，
     * 符合题目要求，返回以此元素为key的map的value和此元素的索引即可
     * b). 如果没有，重复step1，将此元素的值作为key，索引作为value放入map中
     *
     * 时间复杂度O(N)
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum1(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                return new int[]{map.get(nums[i]), i};
            }
            map.put(target - nums[i], i);
        }
        return new int[2];
    }

    public static void main(String[] args) {
        int[] array = new int[]{2, 7, 11, 15};
        int[] result = twoSum(array, 22);
        System.out.println("twoSum:" + Arrays.toString(result));
        result = twoSum1(array, 22);
        System.out.println("twoSum1:" + Arrays.toString(result));
        array = new int[]{3, 2, 4};
        result = twoSum(array, 6);
        System.out.println("twoSum:" + Arrays.toString(result));
        result = twoSum1(array, 6);
        System.out.println("twoSum1:" + Arrays.toString(result));
        array = new int[]{3, 2, 2, 4};
        result = twoSum(array, 6);
        System.out.println("twoSum:" + Arrays.toString(result));
        result = twoSum1(array, 6);
        System.out.println("twoSum1:" + Arrays.toString(result));
    }
}
